package MyBinaryTree;

public class MyBuildBTree {
    /**
     * 利用中序与先序构建二叉树
     * @param preOrder  先序遍历
     * @param inOrder   中序遍历
     * @param pre_start  先序遍历的起点
     * @param pre_end    先序遍历的终点
     * @param in_start   中序的起点
     * @param in_end      中序的终点
     * return 二叉树结点
     */
    public static BiTreeNode MyBuildBTree(String preOrder, String inOrder, int pre_start, int pre_end, int in_start, int in_end) throws InterruptedException {
        // 有结点信息
        if(pre_start > pre_end || in_start > in_end){
            return null;
        }else{
            // 拿到根节点
            char data = preOrder.charAt(pre_start);
            int i = in_start;
            for(; i<=in_end; i++){
                // 寻找一个与根节点相同的结点，此时在中序中，左边是左子树，右边是右子树
                // i+in 就是来对左右子树进行区分查找
                if(inOrder.charAt(i)==data){
                    break;
                }
                // 如果最终没有找到需要匹配的
                if(i == in_end){
                    i=-1;
                    break;
                }
            }
            BiTreeNode root = new BiTreeNode(data);
            // 寻找左子树
            // 对于左子树来看 先序的尾指针 = pre_start + (i-in_start)   先序头指针+左子树的长度
            // 对于左子树来看 中序的尾指针 = i-1   在中序排列中根节点前的一个节点
            root.lchild = MyBuildBTree(preOrder, inOrder, pre_start+1, pre_start+i-in_start, in_start, i-1);
            // 寻找右子树
            root.rchild = MyBuildBTree(preOrder, inOrder, pre_start+i-in_start+1, pre_end, i+1, in_end);

            return root;
        }
    }

    public static void main(String[] args) throws InterruptedException {
        String preOrder = "ABECFG";
        String inOrder = "BEAFCG";
        MyBuildBTree(preOrder, inOrder, 0, 5, 0, 5);

    }

}
